package java学习.算法.动态规划.暴力递归与动态规划;

import java.util.*;

/**
 * **************
 * 项目名称: 蓝桥杯 <br/>
 * 文件名称:  <br/>
 * 文件描述: 这里添加您的类文件描述，说明当前文件要包含的功能。 <br/>
 * 文件创建：刘世锦 <br/>
 * 创建时间: 2022/5/28 <br/>
 *
 * @version v1.0 <br/>
 * @update [序号][日期YYYY-MM-DD][更改人姓名][变更描述]<br/>
 * *************
 */
public class solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *https://blog.nowcoder.net/n/7a67fa8571dd4ee3aeb0860c187437b0
     *
     * @param seed char字符型一维数组 字符种子
     * @param size int整型 验证码长度
     * @return string字符串一维数组
     *
    [0,1,2,3,A],3
    ["012","013","01A","021","023","02A","031",
    "032","03A","0A1","0A2","0A3","102","103",
    "10A","120","123","12A","130","132","13A","1A0",
    "1A2","1A3","201","203","20A","210","213","21A",
    "230","231","23A","2A0","2A1","2A3","301","302",
    "30A","310","312","31A","320","321","32A","3A0",
    "3A1","3A2","A01","A02","A03","A10","A12","A13","A20","A21","A23","A30","A31","A32"]

     */
    public static void main(String[] args) {
        char[] seed= {'0','1','2','3','A'};
        char[] seed1= {'0','1','2'};

        long startTime=System.nanoTime();   //获取开始时间
   //测试的代码段

        System.out.println(Arrays.toString(Permutation(seed, 3)));
        long endTime=System.nanoTime(); //获取结束时间
        System.out.println("程序运行时间： "+(endTime-startTime)+"ns");

        System.out.println(Arrays.toString(getVerificationCode(seed, 3)));

        System.out.println(Arrays.equals(Permutation(seed, 3),getVerificationCode(seed, 3)));
    }
    public static String[] Permutation (char[] seed, int size) {
        // write code here
        List<String> list = new ArrayList<>(
        );

        process(seed,size,0,"",list);
/*
todo
 Collections.sort() 方法主要有如下两种重载形式。
     void sort(List list)：根据元素的自然顺序对集合中的元素进行升序排序。
     void sort(List list,Comparator comparator)：按 comparator 参数指定的排序方式对集合中的元素进行排序。
 */
        Collections.sort(list);
//        Collections.swap();
        System.out.println(list);
        System.out.println(list.size());
        String[] s=  new String[list.size()];
        for (int i = 0; i < s.length; i++) {
            s[i] = list.get(i);
        }
        return s;
    }

    public static void process(char[] seed, int size, int i, String cur,List<String> list) {

        for (int j = i; j < seed.length; j++) {
            if (cur.length()>=size){
                list.add(cur+"");
                cur="";
            }
            swap(seed,i,j);
            process(seed,size,i+1,cur+seed[i],list);
            swap(seed,j,i);

        }


    }

    private static void swap(char[] str, int j, int i) {
        char t = str[i];
        str[i] = str[j];
        str[j] = t;
    }

        public  static  String[] getVerificationCode(char[] seed, int size){
            ArrayList<String> list = new ArrayList<>();
            int n = seed.length;
            boolean[] vis = new boolean[n];
            dfs(seed, n, vis, size, "",list);
            Collections.sort(list);
            String[] ans = new String[list.size()];
            for(int i = 0; i < list.size(); ++i){
                ans[i] = list.get(i);
            }
            return ans;
        }

    public static void dfs(char[] seed, int n, boolean[] vis, int size, String s,ArrayList<String> list){
        if(s.length() == size){
            list.add(s);
            return;
        }
        for(int i = 0; i < n; ++i){
            if(vis[i]){
                continue;
            }
            vis[i] = true;
            dfs(seed, n, vis, size, s + seed[i], list);
            vis[i] = false;
        }
    }

}
